# https://gitee.com/yueyinqiu5990/tj12413601/blob/master/assignment1/question3/interpolations/newton.py
import typing

from question3.interpolation_method import InterpolationMethod1d


class NewtonInterpolation(InterpolationMethod1d):
    def interpolate(
            self,
            points: typing.Iterable[tuple[float, float]]) \
            -> typing.Callable[[float], float]:
        # 在 result_function 中需要用到 x 但不需要 y ，所以在这里分开
        points_x: list[float] = []
        points_y: list[float] = []
        for p_x, p_y in points:
            points_x.append(p_x)
            points_y.append(p_y)
        if len(points_x) < 2:
            raise ValueError(f"Cannot do interpolation with {len(points_x)} point.")

        factors: list[float] = [points_y[0]]
        caches: dict[tuple[float, float], float] = {}
        for i in range(1, len(points_x)):
            factors.append(
                NewtonInterpolation.__divided_difference(
                    points_x, points_y, (0, i), caches))

        def result_function(x: float):
            result = 0
            for r_i in range(len(factors)):
                current = factors[r_i]
                for j in range(r_i):
                    current *= x - points_x[j]
                result += current
            return result

        return result_function

    @staticmethod
    def __divided_difference(
            points_x: list[float],
            points_y: list[float],
            left_and_right: tuple[int, int],
            caches: dict[tuple[float, float], float]):
        if left_and_right in caches:
            return caches[left_and_right]
        left, right = left_and_right
        if left + 1 == right:
            upper = points_y[right] - points_y[left]
        else:
            without_left = NewtonInterpolation.__divided_difference(
                points_x, points_y, (left + 1, right), caches)
            without_right = NewtonInterpolation.__divided_difference(
                points_x, points_y, (left, right - 1), caches)
            upper = without_left - without_right
        lower = points_x[right] - points_x[left]
        result = upper / lower
        caches[left_and_right] = result
        return result
